package Tree.Recursive;

import Utils.Pair;
import Utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 打家劫舍 III: 目前只做了一半，对该树进行了广度优先搜索，可以求得其每层的和
 * Lettcode 337: https://leetcode-cn.com/problems/house-robber-iii/
 */
public class rob {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 1));
        int oddSum = 0;
        int evenSum = 0;
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> pairNode = queue.poll();
            TreeNode node = pairNode.getKey();
            Integer num = pairNode.getValue();
            if (num % 2 == 0) {
                evenSum += node.val;
            } else {
                oddSum += node.val;
            }
            if (node.left != null) {
                queue.add(new Pair<TreeNode, Integer>(node.left, num + 1));
            }
            if (node.right != null) {
                queue.add(new Pair<TreeNode, Integer>(node.right, num + 1));
            }
        }
        return Math.max(oddSum, evenSum);
    }
}
